{
 "metadata": {
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5-final"
  },
  "orig_nbformat": 2,
  "kernelspec": {
   "name": "python3",
   "display_name": "Python 3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2,
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "([1, 6, 12, 15, 50, 90], 4)\n"
     ]
    }
   ],
   "source": [
    "def mysort(lst):\n",
    "    if len(lst) == 1:\n",
    "        return lst,0\n",
    "    else:\n",
    "        n = len(lst) // 2#提取中间数\n",
    "        lst1,count1 = mysort(lst[0:n])#获得左侧数组，带入递归\n",
    "        lst2,count2 = mysort(lst[n:len(lst)+1])#获得右侧数组，带入递归\n",
    "        lst,count = sortandcount(lst1,lst2,0)#讲左侧右侧数组带入sortandcount进行排序以及逆序数的计数\n",
    "        return lst,count1+count2+count\n",
    " \n",
    "def sortandcount(lst1, lst2,count): \n",
    "    i = 0#初始化左侧数组索引\n",
    "    j = 0#初始化右侧数组索引\n",
    "    res = []#存储经过排列后的\n",
    "    while i < len(lst1) and j < len(lst2):#当索引不超过两个列表长度的情况下进行循环\n",
    "        if lst1[i] <= lst2[j]:\n",
    "            res.append(lst1[i])\n",
    "            i += 1\n",
    "        else:\n",
    "            if lst1[i]>3*lst2[j]:\n",
    "                count += len(lst1)-i\n",
    "            res.append(lst2[j])\n",
    "            j += 1\n",
    "    res += lst1[i:]\n",
    "    res += lst2[j:]\n",
    "    return res,count\n",
    " \n",
    " \n",
    "\n",
    "print(mysort([15,6,50,12,1,90])) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ]
}